path: root/js/lost.js

"use strict";
// It's strict!

//
// Helper functions
//

// Just return a random integer between 0 and max, exclusive on the upper bound.
function randInt( max )
{
    return Math.floor(Math.random() * max);
}

// Return the id for the opposite direction of the direction given.
function oppositeDir( iDir )
{
    if( iDir%2 === 1 )
        return iDir-1;
    return iDir+1;
}

//
// Class: Cell
//
function Cell()
{
    this.iDist = 0;
    this.iPath = 0;
    this.iWalls = 0;
}

//
// Class: Position
//
function Position( iDims, ...Vals )
{
    // Store dimension count
    this.iDims = iDims;

    // Check to see if Vals is a non-empty array
    if( Array.isArray(Vals) && Vals.length > 0 )
    {
        // Make sure Vals has the right number of elements
        if( Vals.length != iDims )
        {
            throw new Error(
                'Position must be initialized with no dimensional data, '+
                'or the correct number of elements.');
        }
        
        // If it does have the correct number of elements, just
        // use it instead of creating a new array
        this.aiValues = Vals;
    }
    else
    {
        // We don't have values from the constructor, let's just
        // create a new blank one...
        this.aiValues = new Array( this.iDims );

        // ...and set the position to zero in all dimensions.
        for( let j = 0; j < this.iDims; j++ )
        {
            this.aiValues[j] = 0;
        }
    }
}

Position.prototype.getDims = function getDims()
{
    return this.iDims;
}

Position.prototype.get = function get( iDim )
{
    return this.aiValues[iDim];
}

Position.prototype.set = function set( iDim, iVal )
{
    this.aiValues[iDim] = iVal;
}

Position.prototype.add = function add( iDim, iDelta )
{
    this.aiValues[iDim] += iDelta;
    return this.aiValues[iDim];
}

Position.prototype.translate = function translate( iDim, iDelta )
{
    let tmp = new Position( this.iDims, ...this.aiValues.slice() );
    tmp.add( iDim, iDelta );
    return tmp;
}

Position.prototype.copy = function translate()
{
    return new Position( this.iDims, ...this.aiValues.slice() );
}

//
// Class: Map
//
function Map( Dimensions )
{
    // Store dimensional data
    this.Dimensions = Dimensions;

    // Compute the total number of cells
    let iTotalSize = 1;
    for( let j = 0; j < Dimensions.getDims(); j++ )
    {
        iTotalSize *= Dimensions.get( j );
    }

    // Allocate cell array, and initialize cells
    this.aCell = new Array( iTotalSize );
    for( let j = 0; j < iTotalSize; j++ )
    {
        this.aCell[j] = new Cell();
    }
}

Map.prototype.getDims = function getDims()
{
    return this.Dimensions.getDims();
}

Map.prototype.getSize = function getSize( iDim )
{
    return this.Dimensions.get( iDim );
}

Map.prototype.isInside = function isInside( Position )
{
    if( Position.getDims() != this.Dimensions.getDims() )
    {
        throw new Error(
            'Number of dimensions in map and position do not match.'
            );
    }

    for( let j = 0; j < this.getDims(); j++ )
    {
        if( Position.get( j ) < 0 )
            return false;
        if( Position.get( j ) >= this.Dimensions.get( j ) )
            return false;
    }

    return true;
}

Map.prototype.getIndex = function getIndex( Position )
{
    if( !this.isInside( Position ) )
    {
        throw new Error('Position is outside of map.');
    }

    let iIdx = 0;
    let iScale = 1;
    for( let j = 0; j < this.getDims(); j++ )
    {
        iIdx += Position.get( j ) * iScale;
        iScale *= this.Dimensions.get( j );
    }
    return iIdx;
}

Map.prototype.get = function get( Position )
{
    return this.aCell[this.getIndex( Position )];
}

Map.prototype.connect = function connect( iWormId1, iWormId2 )
{
    let p = new Position( this.getDims() );
    let pMax1 = null;
    let pMax2 = null;
    let iDistMax = 0;
    let iDirMax = 0;

    let iDim = 0;
    for(;;)
    {
        let c = this.get( p );
        if( c.iPath === iWormId1 || c.iPath === iWormId2 )
        {
            // This cell is one of the two paths we want to connect, let's
            // see if there's a cell from the other path nearby.
            for( iDim = 0; iDim < this.getDims(); iDim++ )
            {
                // Look 'down' in the current dimension
                let t = p.translate( iDim, -1 );
                for( let iDir = 0; iDir < 2; iDir++ )
                {
                    // Is the current position inside the maze?
                    if( t.get( iDim ) >= 0 &&
                        t.get( iDim ) < this.getSize( iDim ) )
                    {
                        // Get cell here.
                        let c2 = this.get( t );
                        if( c.iPath !== c2.iPath &&
                            (c2.iPath === iWormId1 || c2.iPath === iWormId2 ) )
                        {
                            let iDist = c.iDist + c2.iDist;
                            if( iDist > iDistMax )
                            {
                                iDistMax = iDist;
                                pMax1 = p.copy();
                                pMax2 = t.copy();
                                iDirMax = iDim*2+iDir;
                            }
                        }
                    }

                    // Look the other direction
                    t.add( iDim, 2 );
                }
            }
        }

        // This is the rediculous engine that lets us iterate through
        // the entire maze, one cell at a time.  This basically increments our
        // position by one, but wraps at the edges of the maze.
        for( iDim = 0; iDim < this.getDims(); iDim++ )
        {
            let iNewVal = p.add( iDim, 1 );
            if( iNewVal < this.getSize( iDim ) )
                break;
            p.set( iDim, 0 );
        }

        // If we ran out of dimensions then it means that we hit the last
        // cell in the grid.
        if( iDim == this.getDims() )
            break;
    }

    this.get( pMax1 ).iWalls |= (1<<iDirMax);
    this.get( pMax2 ).iWalls |= (1<<oppositeDir(iDirMax));
}

//
// Class: Vector
//
function Vector( pPos, iDir )
{
    this.pPos = pPos;
    this.iDir = iDir;
}

//
// Class: Worm
//
function Worm( iId, pStart, rMap )
{
    // Initialize basic state, we start with distance set to 1
    this.iId = iId;
    this.pPosition = pStart;
    this.rMap = rMap;
    this.iDist = 1;

    // Setup walls here to create an opening.  We're only going to do
    // this on the first two dimensions.  This assumes that we have at least
    // two dimensions, which I feel like is a safe assumption. 1d mazes are...
    // pretty easy.
    let iDirs = [];
    if( this.pPosition.get( 0 ) === 0 )
        iDirs.push( 1 );
    else if( this.pPosition.get( 0 ) === this.rMap.getSize( 0 )-1 )
        iDirs.push( 2 );

    if( this.pPosition.get( 1 ) === 0 )
        iDirs.push( 4 );
    else if( this.pPosition.get( 1 ) === this.rMap.getSize( 1 )-1 )
        iDirs.push( 8 );

    // Now that we know if we're near a wall in the first two demensions
    // do something with that
    if( iDirs.length > 0 )
    {
        // We are near a wall, pick a random wall to open a hole in
        this.rMap.get(this.pPosition).iWalls |= iDirs[randInt(iDirs.length)];
        this.rMap.get(this.pPosition).iPath = this.iId;
    }
}

Worm.prototype.timestep = function timestep()
{
    // Handy to reference how many dimensions we have
    let iDims = this.rMap.getDims();

    // Possible directions
    let pDirs = [];

    for(;;)
    {
        let pBack = null;
        for( let j = 0; j < iDims; j++ )
        {
            let iSize = this.rMap.getSize( j );
            let pPos = this.pPosition.translate( j, -1 );
            if( pPos.get( j ) >= 0 )
            {
                let xCell = this.rMap.get( pPos );
                if( xCell.iPath === 0 )
                {
                    pDirs.push( new Vector( pPos, j*2 ) );
                }
                else if( xCell.iPath === this.iId &&
                        xCell.iDist === this.iDist-1 )
                {
                    pBack = pPos;
                }
            }

            pPos = this.pPosition.translate( j, 1 );
            if( pPos.get( j ) < iSize )
            {
                let xCell = this.rMap.get( pPos );
                if( xCell.iPath === 0 )
                {
                    pDirs.push( new Vector( pPos, j*2+1 ) );
                }
                else if( xCell.iPath === this.iId &&
                        xCell.iDist === this.iDist-1 )
                {
                    pBack = pPos;
                }
            }
        }

        if( pDirs.length > 0 )
        {
            break;
        }
        else
        {
            if( pBack !== null )
            {
                this.pPosition = pBack;
                this.iDist--;
            }
            else
            {
                return false;
            }
        }
    }

    let iSel = randInt( pDirs.length );
    let cCur = this.rMap.get( this.pPosition );
    cCur.iWalls |= (1<<pDirs[iSel].iDir);
    let cNext = this.rMap.get( pDirs[iSel].pPos );
    cNext.iWalls |= (1<<oppositeDir( pDirs[iSel].iDir ));
    cNext.iDist = ++this.iDist;
    cNext.iPath = this.iId;
    this.pPosition = pDirs[iSel].pPos;

    return true;
}

//
// Class: Render
//
function Render( rMap, eParent )
{
    this.rMap = rMap;
    this.eParent = eParent;
}

Render.prototype.render = function render()
{
}

//
// Class: RenderCanvas2D
//
function RenderCanvas2D( rMap, eParent )
{
    Render.call( this, rMap, eParent );

    this.eCanvas = null;
    this.ctx = null;

    this.pExtPosition = new Position( rMap.getDims() );

    this.iIconSize = 11;
    this.iBorder = 3;
    this.iCellSize =
        this.iBorder +
        (this.rMap.getDims()-2)*2*(this.iIconSize+this.iBorder);
    
    this.eCanvas = document.createElement('canvas');
    this.eCanvas.width = this.iCellSize*this.rMap.getSize( 0 );
    this.eCanvas.height = this.iCellSize*this.rMap.getSize( 1 );
    eParent.appendChild( this.eCanvas );
    this.ctx = this.eCanvas.getContext("2d");
    this.ctx.lineWidth = 1.0;

    this.render();

    let btnBox = document.createElement('div');
    eParent.appendChild( document.createElement('br') );
    eParent.appendChild( document.createElement('br') );
    eParent.appendChild( btnBox );

    for( let j = 2; j < this.rMap.getDims(); j++ )
    {
        for( let k = 0; k < this.rMap.getSize( j ); k++ )
        {
            let btn = document.createElement('button');
            btn.addEventListener(
                'click',
                RenderCanvas2D.prototype.setFloor.bind(
                    this,
                    [k]
                    )
                );
            btn.appendChild(
                document.createTextNode('Floor ' + (k+1) )
                );
            btnBox.appendChild( btn );
        }
    }
}

RenderCanvas2D.prototype = Object.create(Render.prototype);
RenderCanvas2D.prototype.constructor = RenderCanvas2D;

RenderCanvas2D.prototype.render = function render()
{
    let iSize = this.iCellSize;
    this.ctx.clearRect( 0, 0, this.eCanvas.width, this.eCanvas.height );
    this.ctx.beginPath();

    let p = this.pExtPosition.copy();
    {
        for( let x = 0; x < this.rMap.getSize( 0 ); x++ )
        {
            for( let y = 0; y < this.rMap.getSize( 1 ); y++ )
            {
                p.set( 0, x );
                p.set( 1, y );
                let c = this.rMap.get( p );
                if( (c.iWalls&1) === 0 && x === 0)
                {
                    this.ctx.moveTo( x*iSize, y*iSize );
                    this.ctx.lineTo( x*iSize, (y+1)*iSize );
                }
                if( (c.iWalls&2) === 0 )
                {
                    this.ctx.moveTo( (x+1)*iSize, y*iSize );
                    this.ctx.lineTo( (x+1)*iSize, (y+1)*iSize );
                }
                if( (c.iWalls&4) === 0 && y === 0)
                {
                    this.ctx.moveTo( x*iSize, y*iSize );
                    this.ctx.lineTo( (x+1)*iSize, y*iSize );
                }
                if( (c.iWalls&8) === 0 )
                {
                    this.ctx.moveTo( x*iSize, (y+1)*iSize );
                    this.ctx.lineTo( (x+1)*iSize, (y+1)*iSize );
                }

                if( (c.iWalls&16) !== 0 )
                {
                    // Up
                    let bx = x*iSize+this.iBorder;
                    let by = y*iSize+this.iBorder;
                    this.ctx.moveTo(
                        bx,
                        by+this.iIconSize
                        );
                    this.ctx.lineTo(
                        bx+this.iIconSize/2,
                        by
                        );
                    this.ctx.lineTo(
                        bx+this.iIconSize,
                        by+this.iIconSize
                        );
                }
                if( (c.iWalls&32) !== 0 )
                {
                    // Down
                    let bx = x*iSize+this.iBorder*2+this.iIconSize;
                    let by = y*iSize+this.iBorder;
                    this.ctx.moveTo(
                        bx,
                        by
                        );
                    this.ctx.lineTo(
                        bx+this.iIconSize/2,
                        by+this.iIconSize
                        );
                    this.ctx.lineTo(
                        bx+this.iIconSize,
                        by
                        );
                }
            }
        }
    }
    this.ctx.stroke();
}

RenderCanvas2D.prototype.setFloor = function setFloor( aFloor )
{
    for( let j = 0; j < aFloor.length; j++ )
    {
        this.pExtPosition.set( j+2, aFloor[j] );
    }
    this.render();
}

//
// Initialize
//
let p = new Position( 3, 15, 15, 3 );
let m = new Map( p );
let exit1 = new Position( p.getDims() );
let exit2 = new Position( p.getDims() );
exit2.set( 1, p.get( 1 )-1 );
let w = [
    new Worm( 1, exit1, m ),
    new Worm( 2, exit2, m )
    ];

do
{
    for( let j = 0; j < w.length; j++ )
    {
        if( !w[j].timestep() )
        {
            w.splice( j, 1 );
            j--;
        }
    }
} while( w.length > 0 );

m.connect( 1, 2 );

let rend = new RenderCanvas2D( m, document.body );
//rend.render( document.body );